{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Moves to Spread Stones Over Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumMoves"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #将石头分散到网格图的最少移动次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>3 * 3</code>&nbsp;，下标从 <strong>0</strong>&nbsp;开始的二维整数矩阵&nbsp;<code>grid</code>&nbsp;，分别表示每一个格子里石头的数目。网格图中总共恰好有&nbsp;<code>9</code>&nbsp;个石头，一个格子里可能会有 <strong>多个</strong>&nbsp;石头。</p>\n",
    "\n",
    "<p>每一次操作中，你可以将一个石头从它当前所在格子移动到一个至少有一条公共边的相邻格子。</p>\n",
    "\n",
    "<p>请你返回每个格子恰好有一个石头的 <strong>最少移动次数</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/23/example1-3.svg\" style=\"width: 401px; height: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,1,0],[1,1,1],[1,2,1]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>让每个格子都有一个石头的一个操作序列为：\n",
    "1 - 将一个石头从格子 (2,1) 移动到 (2,2) 。\n",
    "2 - 将一个石头从格子 (2,2) 移动到 (1,2) 。\n",
    "3 - 将一个石头从格子 (1,2) 移动到 (0,2) 。\n",
    "总共需要 3 次操作让每个格子都有一个石头。\n",
    "让每个格子都有一个石头的最少操作次数为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/08/23/example2-2.svg\" style=\"width: 401px; height: 281px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>grid = [[1,3,0],[1,0,0],[1,0,3]]\n",
    "<b>输出：</b>4\n",
    "<b>解释：</b>让每个格子都有一个石头的一个操作序列为：\n",
    "1 - 将一个石头从格子 (0,1) 移动到 (0,2) 。\n",
    "2 - 将一个石头从格子 (0,1) 移动到 (1,1) 。\n",
    "3 - 将一个石头从格子 (2,2) 移动到 (1,2) 。\n",
    "4 - 将一个石头从格子 (2,2) 移动到 (2,1) 。\n",
    "总共需要 4 次操作让每个格子都有一个石头。\n",
    "让每个格子都有一个石头的最少操作次数为 4 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>grid.length == grid[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 9</code></li>\n",
    "\t<li><code>grid</code>&nbsp;中元素之和为&nbsp;<code>9</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-moves-to-spread-stones-over-grid](https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-moves-to-spread-stones-over-grid](https://leetcode.cn/problems/minimum-moves-to-spread-stones-over-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0],[1,1,1],[1,2,1]]', '[[1,3,0],[1,0,0],[1,0,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        s = list(s)\n",
    "        ans = 0\n",
    "        for i, ch in enumerate(s):\n",
    "            if ch == 'X':\n",
    "                ans += 1\n",
    "                idx = i\n",
    "                while idx < n and idx - i < 3:\n",
    "                    s[idx] = '0'\n",
    "                    idx += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        c = -1\n",
    "        for i, v in enumerate(s):\n",
    "            if v == \"X\" and i > c:\n",
    "                ans += 1\n",
    "                c = i + 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        times = 0\n",
    "        remain = 0\n",
    "        for char in s:\n",
    "            if char == 'X' and remain <= 0:\n",
    "                times += 1\n",
    "                remain = 2\n",
    "            else:\n",
    "                remain -= 1\n",
    "        return times\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        covered = -1\n",
    "        res=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c=='X' and i>covered:\n",
    "                res +=1\n",
    "                covered = i+2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        covered = -1\n",
    "        res = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'X' and i > covered:\n",
    "                res += 1\n",
    "                covered = i + 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        # count = 0\n",
    "        # for i in range(0,len(s)-1,1):\n",
    "        #     if \"X\" in s[i:i+3]:\n",
    "        #         s = s[i:i+3].replace(\"X\",\"0\")\n",
    "        #         count += 1\n",
    "        # return count\n",
    "        i = 0\n",
    "        count = 0\n",
    "        while(i<len(s)):\n",
    "            if s[i] == 'X':\n",
    "                i += 3\n",
    "                count += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        _result = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                _result += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return _result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        for i in range(n-2):\n",
    "            if  s[i] == 'X':\n",
    "                cnt += 1\n",
    "                s[i] = s[i+1] = s[i+2] = 'O'\n",
    "        return cnt + int(s[-1] == 'X' or s[-2] == 'X')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans,l,idx = 0,len(s),s.find('X')\n",
    "        while idx < l:\n",
    "            if s[idx] == 'X':\n",
    "                idx += 3\n",
    "                ans += 1\n",
    "            else:\n",
    "                idx += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i=0\n",
    "        num=0\n",
    "        while i<len(s):\n",
    "            if s[i]=='X':\n",
    "                num+=1\n",
    "                i+=3\n",
    "            else:\n",
    "                i+=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        index = 0\n",
    "        ans = 0\n",
    "        while index < len(s):\n",
    "            if s[index] == \"X\":\n",
    "                ans += 1\n",
    "                index += 3\n",
    "            else:\n",
    "                index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        tmp = list(s)\n",
    "        if set(tmp) == {'O'}:\n",
    "            return 0 \n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            if s[i] == \"X\":\n",
    "                res += 1\n",
    "                i += 2\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count=0\n",
    "        if len(s)<4:\n",
    "            return 1\n",
    "        i=0\n",
    "        while i<len(s):\n",
    "            if s[i]==\"X\":\n",
    "                i+=3\n",
    "                count+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<n:\n",
    "            if s[i]=='X':\n",
    "                ans+=1\n",
    "                i+=3\n",
    "            else:\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        r = 0\n",
    "        d = -1\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'X' and i > d:\n",
    "                r += 1\n",
    "                d = i + 2\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        c = 0\n",
    "        while True:\n",
    "            s = s.strip('O')\n",
    "            m = re.search(r'(XXX|XOX|XXO|XOO|XX|X)', s)\n",
    "            if not m:\n",
    "                break\n",
    "            a, b = m.span()\n",
    "            s = s[:a] + 'OOO' + s[b:]\n",
    "            c += 1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count = 0\n",
    "        i = 0\n",
    "        while i < (len(s)):\n",
    "            if s[i] == 'X':\n",
    "                count += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        t = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'X':\n",
    "                t+=1\n",
    "                i+=3\n",
    "        return t'''\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                cnt += 1\n",
    "                i = i + 3\n",
    "            else: i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 2\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        a = len(s)\n",
    "        ans = num = 0\n",
    "        while num < a:\n",
    "            if s[num] == 'X':\n",
    "                num += 3\n",
    "                ans += 1\n",
    "            else:\n",
    "                num += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        t = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == 'X':\n",
    "                t+=1\n",
    "                i+=3\n",
    "        return t'''\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        cur = 0\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        while cur < n:\n",
    "            if s[cur] == 'X':\n",
    "                ans += 1\n",
    "                cur += 2\n",
    "            cur += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        c = 0\n",
    "        while True:\n",
    "            s = s.strip('O')\n",
    "            m = re.search(r'(XXX|XOX|XXO|OOX|OXO|XOO|OXX|XX|X)', s)\n",
    "            if not m:\n",
    "                break\n",
    "            a, b = m.span()\n",
    "            s = s[:a] + 'OOO' + s[b:]\n",
    "            c += 1\n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i=0\n",
    "        num=0\n",
    "        while i<len(s):\n",
    "            if s[i]=='X':\n",
    "                num+=1\n",
    "                i+=3\n",
    "            else:\n",
    "                i+=1\n",
    "        return num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans, j = 0, 0\n",
    "        while j < len(s):\n",
    "            if s[j] == \"X\":\n",
    "                ans += 1\n",
    "                j += 3\n",
    "            else:\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count=0\n",
    "        while s.find('X')>-1:\n",
    "            count+=1\n",
    "            if s.find('X')+3>=len(s):\n",
    "                return count\n",
    "            else:\n",
    "                s=s[s.find('X')+3:]\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i<len(s):\n",
    "            if s[i]=='X':\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                i += 2\n",
    "                ans += 1\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        res, i = 0, 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                res += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans, j = 0, 0\n",
    "        while j < len(s):\n",
    "            if s[j] == \"X\":\n",
    "                ans += 1\n",
    "                j += 2\n",
    "            j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<len(s):\n",
    "            if s[i]=='X':\n",
    "                i+=3\n",
    "                ans+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i=0\n",
    "        ans=0\n",
    "        while i<len(s):\n",
    "            if s[i]==\"X\":\n",
    "                ans+=1\n",
    "                i+=2\n",
    "            i+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count=0\n",
    "        i=0\n",
    "        while i<len(s):\n",
    "            if s[i]=='X':\n",
    "                count+=1\n",
    "                i+=3\n",
    "                continue\n",
    "            i+=1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count=0\n",
    "        i=0\n",
    "        while i < len(s):            \n",
    "            if s[i]=='X':\n",
    "                count+=1\n",
    "                i+=3\n",
    "            else:               \n",
    "                i+=1            \n",
    "        return count\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ret,pre = 0,-10\n",
    "        for i,c in enumerate(s):\n",
    "            if c=='X' and pre+2<i:\n",
    "                pre,ret = i,ret+1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        lenth=len(s)\n",
    "        count=0\n",
    "        i=0\n",
    "        while i<lenth:\n",
    "            index=s[i::].find('X')\n",
    "            if index==-1:\n",
    "                break\n",
    "            count+=1\n",
    "            i=i+3+index\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        covered=-1\n",
    "        res=0\n",
    "        for i,c in enumerate(s):\n",
    "            if c=='X' and i>covered:\n",
    "                res+=1\n",
    "                covered=i+2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        count = 0\n",
    "        ans = 0\n",
    "        while count < len(s):\n",
    "            if \"X\" == s[count]:\n",
    "                count += 3\n",
    "                ans += 1\n",
    "            else:\n",
    "                count += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        最少操作次数 = 0\n",
    "        x = 0\n",
    "        while x < n:\n",
    "            if s[x] == \"X\":\n",
    "                x += 3\n",
    "                最少操作次数 += 1\n",
    "            else:\n",
    "                x += 1 \n",
    "        return 最少操作次数"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        if len(s)<3:return 0\n",
    "        covered = -1\n",
    "        res = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c=='X' and i>covered:\n",
    "                res += 1\n",
    "                covered = i+2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        res=0\n",
    "        i=0\n",
    "        while i<n:\n",
    "            if s[i]==\"X\":\n",
    "                res+=1\n",
    "                i+=3\n",
    "            else:\n",
    "                i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        n = len(s)\n",
    "        res = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i] == 'X':\n",
    "                res += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "      count = 0\n",
    "      left = 0\n",
    "      right = left + 2\n",
    "      _len = len(s)\n",
    "\n",
    "      while right < _len:\n",
    "        _s = s[left:right+1]\n",
    "        print(_s)\n",
    "\n",
    "        if s[left] == 'X':\n",
    "          count += 1\n",
    "          left = right + 1\n",
    "          right = left + 2\n",
    "          continue\n",
    "        \n",
    "        left += 1\n",
    "        right += 1\n",
    "\n",
    "      \n",
    "      _s = s[left:]\n",
    "      print(f'last {_s}')\n",
    "\n",
    "      if _s is not None and 'X' in _s:\n",
    "        count += 1\n",
    "\n",
    "      return count\n",
    "      \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        s_list = list(s)\n",
    "        n = len(s_list)\n",
    "        count = 0\n",
    "        # print(s_list)\n",
    "        if (n-3) >= 1:\n",
    "            for i in range(n-2):\n",
    "                if s_list[i] == \"X\":\n",
    "                    count += 1\n",
    "                    s_list[i], s_list[i+1], s_list[i+2] = \"O\", \"O\", \"O\"\n",
    "        else:\n",
    "            if 'X' in s:\n",
    "                return 1\n",
    "            else:\n",
    "                return 0 \n",
    "        \n",
    "        if \"X\" in s_list[-2:]:\n",
    "            count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        transform = 0\n",
    "        while 1:\n",
    "            while 1:\n",
    "                if s == None or len(s) == 1:\n",
    "                    break\n",
    "                if s[0] == \"O\":\n",
    "                    s = s[1:]\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "            if len(s) % 3 == 0:\n",
    "                s = s\n",
    "            elif len(s) % 3 == 1:\n",
    "                s = s + \"OO\"\n",
    "            elif len(s) % 3 == 2:\n",
    "                s = s + \"O\"\n",
    "\n",
    "            if s[0:3] != \"OOO\" and len(s) != 3:\n",
    "                transform = transform + 1\n",
    "                s=s[3:]\n",
    "            elif s[0:3] != \"OOO\" and len(s) == 3:\n",
    "                transform = transform + 1\n",
    "                return transform\n",
    "            elif len(s) == 3:\n",
    "                return transform\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        s = list(s)\n",
    "        ret = 0\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            if s[i] == 'X':\n",
    "                ret += 1\n",
    "                if i + 1 < n:\n",
    "                    s[i + 1] = 'O'\n",
    "                if i + 2 < n:\n",
    "                    s[i + 2] = 'O'\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n",
    "\n",
    "        # def zhuan(str):\n",
    "        #     for i in range(3):\n",
    "        #         str[i]='O'\n",
    "        #      return str\n",
    "        # str=list(input())\n",
    "        # len=len(str)\n",
    "        # count=0\n",
    "        # for i in range(len):\n",
    "        #     if str[i]=='X':\n",
    "        #         str=zhuan(str)\n",
    "        #         i=i+3\n",
    "        #         count+=1\n",
    "        # print(count)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        covered = -1\n",
    "        ans = 0\n",
    "        for i,c in enumerate(s):\n",
    "            if c == \"X\" and i > covered:\n",
    "                ans += 1\n",
    "                covered = i + 2\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        ans = i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == \"X\":\n",
    "                ans += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        covered = -1\n",
    "        res = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if c == 'X' and i > covered:\n",
    "                res += 1\n",
    "                covered = i + 2\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        pointer = 0\n",
    "        answer = 0\n",
    "        while pointer < n:\n",
    "            if s[pointer] == 'X':\n",
    "                pointer += 3\n",
    "                answer += 1\n",
    "            else:\n",
    "                pointer += 1\n",
    "        return answer    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == 'X':\n",
    "                cnt += 1\n",
    "                i += 3\n",
    "            else:\n",
    "                i += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        i=count=0\n",
    "        n = len(s)\n",
    "        while i<n:\n",
    "            if s[i]==\"X\":\n",
    "                count+=1\n",
    "                i+=2\n",
    "            i+=1\n",
    "        return count\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        index = 0\n",
    "        while index < n:\n",
    "            if s[index] == 'X':\n",
    "                ans += 1\n",
    "                index += 3\n",
    "            else:\n",
    "                index += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, s: str) -> int:\n",
    "        a=i=0\n",
    "        while i <len(s):\n",
    "            if s[i] == \"X\":\n",
    "                a+=1\n",
    "                i+=3\n",
    "            else:\n",
    "                i+=1\n",
    "        return a\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        比较麻烦的是引入了旋转机制\n",
    "        怎么更好地还原？\n",
    "        一、表示贪吃蛇状态，需要多加一维\n",
    "        然后开始跑dfs，注意要好好模拟是否可达\n",
    "        另外，用dis表示蛇头和状态\n",
    "        '''\n",
    "        n=len(grid)\n",
    "        dis=[[[inf]*n for _ in range(n) ]for _ in range(2)]\n",
    "        dis[0][0][1]=0 #0表示水平\n",
    "        q=deque([(0,1,0)])\n",
    "        def move(i:int,j:int,k:int)->None:\n",
    "            if i<n and j<n and not grid[i][j] and d+1<dis[k][i][j]:\n",
    "                    q.append((i,j,k))\n",
    "                    dis[k][i][j]=d+1\n",
    "        while q:\n",
    "            x,y,z=q.popleft()\n",
    "            d=dis[z][x][y]\n",
    "            if z==0:\n",
    "                #水平移动\n",
    "                move(x, y+1, z)\n",
    "                #竖直移动和旋转移动\n",
    "                if x+1<n and y-1>=0 and not grid[x+1][y] and not grid[x+1][y-1]:\n",
    "                    move(x+1,y,0)\n",
    "                    move(x+1,y-1,1)\n",
    "            else:\n",
    "                #竖直移动\n",
    "                move(x+1,y,z)\n",
    "                #水平移动和旋转移动\n",
    "                if y+1<n and x-1>=0 and not grid[x][y+1] and not grid[x-1][y+1]:\n",
    "                    move(x,y+1,1)\n",
    "                    move(x-1,y+1,0)\n",
    "        if dis[0][n-1][n-1]<inf:\n",
    "                return dis[0][n-1][n-1]\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        比较麻烦的是引入了旋转机制\n",
    "        怎么更好地还原？\n",
    "        一、表示贪吃蛇状态，需要多加一维\n",
    "        然后开始跑dfs，注意要好好模拟是否可达\n",
    "        另外，用dis表示蛇头和状态\n",
    "        '''\n",
    "\n",
    "        '''\n",
    "        优雅的代码，往往只需要一种移动方式\n",
    "        发现用蛇尾判断似乎更加简单\n",
    "        '''\n",
    "        n=len(grid)\n",
    "        dis=[[[inf]*n for _ in range(n) ]for _ in range(2)]\n",
    "        dis[0][0][0]=0 #0表示水平\n",
    "        q=deque([(0,0,0)])\n",
    "        while q:\n",
    "            x,y,z=q.popleft()\n",
    "            d=dis[z][x][y]\n",
    "            for (i,j,k) in (x+1,y,z),(x,y+1,z),(x,y,z^1):\n",
    "                i2,j2=i+k,j+(k^1)\n",
    "                if i2<n and j2<n and d+1<dis[k][i][j] and grid[i][j]==0 and grid[i2][j2]==0 and (k==z or grid[x+1][y+1]==0):\n",
    "                    dis[k][i][j]=d+1\n",
    "                    q.append((i,j,k))\n",
    "\n",
    "        if dis[0][n-1][n-2]<inf:\n",
    "                return dis[0][n-1][n-2]\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n =  len(grid)\n",
    "        dis = [[[-1] * n for _ in range(n)] for _ in range(2)]\n",
    "        dis[0][0][0] = 0\n",
    "        q = deque()\n",
    "        q.append((0, 0, 0))\n",
    "        while q:\n",
    "            flag, x, y = q.popleft()\n",
    "            for f, nx, ny in (flag, x + 1, y), (flag, x, y + 1), (flag ^ 1, x, y):\n",
    "                # 计算蛇另一端位置\n",
    "                nxx, nyy = nx + f, ny + (f ^ 1)\n",
    "                if nxx < n and nyy < n and grid[nx][ny] == 0 \\\n",
    "                    and grid[nxx][nyy] == 0 and (f == flag or grid[nx + 1][ny + 1] == 0) \\\n",
    "                        and dis[f][nx][ny] == -1:\n",
    "                    dis[f][nx][ny] = dis[flag][x][y] + 1\n",
    "                    if nx == n - 1 and ny == n - 2:\n",
    "                        return dis[f][nx][ny]\n",
    "                    q.append((f, nx, ny))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        vis = [[[True]*2 for _ in range(n) ]for _ in range(n)]\n",
    "        q = deque([(0,0,0,0)])\n",
    "        vis[0][0][0] = False\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            res+=1\n",
    "            x,y,z,d = q.popleft()\n",
    "            if x==n-1 and y==n-2 and z==0:\n",
    "                print(res)\n",
    "                return d\n",
    "            if z == 0:\n",
    "                if y+2 < n and grid[x][y+2]==0 and vis[x][y+1][0]:\n",
    "                    vis[x][y+1][0] = False\n",
    "                    q.append((x,y+1,0,d+1))\n",
    "                if x+1<n and grid[x+1][y]==grid[x+1][y+1]==0:\n",
    "                    if vis[x+1][y][0]:\n",
    "                        vis[x+1][y][0] = False\n",
    "                        q.append((x+1,y,0,d+1))\n",
    "                    if vis[x][y][1]:\n",
    "                        vis[x][y][1] = False\n",
    "                        q.append((x,y,1,d+1))\n",
    "            else:\n",
    "                if x+2 < n and grid[x+2][y] == 0 and vis[x+1][y][1]:\n",
    "                    vis[x+1][y][1] = False\n",
    "                    q.append((x+1, y, 1, d+1))\n",
    "                if y+1<n and grid[x][y+1]==grid[x+1][y+1]==0:\n",
    "                    if vis[x][y+1][1]:\n",
    "                        vis[x][y+1][1] = False\n",
    "                        q.append((x,y+1,1,d+1))\n",
    "                    if vis[x][y][0]:\n",
    "                        vis[x][y][0] = False\n",
    "                        q.append((x,y,0,d+1))\n",
    "        print(res)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        vis = [[[True]*2 for _ in range(n) ]for _ in range(n)]\n",
    "        q = [(0,0,0,0)]\n",
    "        vis[0][0][0] = False\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            res+=1\n",
    "            x,y,z,d = q.pop(0)\n",
    "            if x==n-1 and y==n-2 and z==0:\n",
    "                print(res)\n",
    "                return d\n",
    "            if z == 0:\n",
    "                if y+2 < n and grid[x][y+2]==0 and vis[x][y+1][0]:\n",
    "                    vis[x][y+1][0] = False\n",
    "                    q.append((x,y+1,0,d+1))\n",
    "                if x+1<n and grid[x+1][y]==grid[x+1][y+1]==0:\n",
    "                    if vis[x+1][y][0]:\n",
    "                        vis[x+1][y][0] = False\n",
    "                        q.append((x+1,y,0,d+1))\n",
    "                    if vis[x][y][1]:\n",
    "                        vis[x][y][1] = False\n",
    "                        q.append((x,y,1,d+1))\n",
    "            else:\n",
    "                if x+2 < n and grid[x+2][y] == 0 and vis[x+1][y][1]:\n",
    "                    vis[x+1][y][1] = False\n",
    "                    q.append((x+1, y, 1, d+1))\n",
    "                if y+1<n and grid[x][y+1]==grid[x+1][y+1]==0:\n",
    "                    if vis[x][y+1][1]:\n",
    "                        vis[x][y+1][1] = False\n",
    "                        q.append((x,y+1,1,d+1))\n",
    "                    if vis[x][y][0]:\n",
    "                        vis[x][y][0] = False\n",
    "                        q.append((x,y,0,d+1))\n",
    "        print(res)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        vis = [[[True]*2 for _ in range(n) ]for _ in range(n)]\n",
    "        q = [(0,0,0,0)]\n",
    "        vis[0][0][0] = False\n",
    "        res = 0\n",
    "        while len(q):\n",
    "            res+=1\n",
    "            x,y,z,d = q.pop(0)\n",
    "            if x==n-1 and y==n-2 and z==0:\n",
    "                return d\n",
    "            if z == 0:\n",
    "                if y+2 < n and grid[x][y+2]==0 and vis[x][y+1][0]:\n",
    "                    vis[x][y+1][0] = False\n",
    "                    q.append((x,y+1,0,d+1))\n",
    "                if x+1<n and grid[x+1][y]==grid[x+1][y+1]==0:\n",
    "                    if vis[x+1][y][0]:\n",
    "                        vis[x+1][y][0] = False\n",
    "                        q.append((x+1,y,0,d+1))\n",
    "                    if vis[x][y][1]:\n",
    "                        vis[x][y][1] = False\n",
    "                        q.append((x,y,1,d+1))\n",
    "            else:\n",
    "                if x+2 < n and grid[x+2][y] == 0 and vis[x+1][y][1]:\n",
    "                    vis[x+1][y][1] = False\n",
    "                    q.append((x+1, y, 1, d+1))\n",
    "                if y+1<n and grid[x][y+1]==grid[x+1][y+1]==0:\n",
    "                    if vis[x][y+1][1]:\n",
    "                        vis[x][y+1][1] = False\n",
    "                        q.append((x,y+1,1,d+1))\n",
    "                    if vis[x][y][0]:\n",
    "                        vis[x][y][0] = False\n",
    "                        q.append((x,y,0,d+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, g: List[List[int]]) -> int:\n",
    "        step, n = 1, len(g)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]  # 初始位置\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):  # 直接把移动后的位置算出来\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)  # 蛇头\n",
    "                    if x2 < n and y2 < n and t not in vis and \\\n",
    "                       g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2:  # 此时蛇头一定在 (n-1,n-1)\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, g: List[List[int]]) -> int:\n",
    "        step, n = 1, len(g)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]  # 初始位置\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):  # 直接把移动后的位置算出来\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)  # 蛇头\n",
    "                    if x2 < n and y2 < n and t not in vis and \\\n",
    "                       g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2:  # 此时蛇头一定在 (n-1,n-1)\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def minimumMoves(self, g: List[List[int]]) -> int:\n",
    "        step, n = 1, len(g)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)] # 初始位置\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1): #直接把移动后的位置抢回来\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1) #蛇头\n",
    "                    if x2 < n and y2 < n and t not in vis and g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2: #此时舌头一定在(n-1,n-1)\n",
    "                            return step # 返回步数计数结果\n",
    "                        vis.add(t) \n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: list[list[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        # 0 for horizontal, 1 for vertical\n",
    "        q = deque([(0,0,0,0)])\n",
    "        vis = {(0,0,0)}\n",
    "\n",
    "        def append(pos):\n",
    "            t = (pos[0],pos[1],pos[2])\n",
    "            if t not in vis:\n",
    "                vis.add(t)\n",
    "                q.append(pos)\n",
    "\n",
    "        while q:\n",
    "            x, y, t, s = q.popleft()\n",
    "            if x == n-1 and y == n-2 and t == 0:\n",
    "                return s\n",
    "            if t: # vertical\n",
    "                if y+1<n and grid[x][y+1]==0 and grid[x+1][y+1]==0:\n",
    "                    append((x,y+1,t,s+1))\n",
    "                    append((x,y,0,s+1))\n",
    "                if x+2<n and grid[x+2][y]==0:\n",
    "                    append((x+1,y,t,s+1))\n",
    "            else: # horizontal\n",
    "                if x+1<n and grid[x+1][y]==0 and grid[x+1][y+1]==0:\n",
    "                    append((x+1,y,t,s+1))\n",
    "                    append((x,y,1,s+1))\n",
    "                if y+2<n and grid[x][y+2]==0:\n",
    "                    append((x,y+1,t,s+1))\n",
    "        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        tag = set()\n",
    "        step = 1\n",
    "        tail = (0, 0, 0)\n",
    "        que = [tail]\n",
    "        tag.add(tail)\n",
    "        while que:\n",
    "            temp = que\n",
    "            que = []\n",
    "            for cur in temp:\n",
    "                x = cur[0]\n",
    "                y = cur[1]\n",
    "                dir = cur[2]\n",
    "                if not dir:\n",
    "                    if y + 2 < n and grid[x][y + 2] != 1:\n",
    "                        if (x, y + 1, 0) not in tag:\n",
    "                            tag.add((x, y + 1, 0))\n",
    "                            que.append((x, y + 1, 0))\n",
    "                            if x == n - 1 and y + 1 == n - 2:\n",
    "                                return step\n",
    "                    if x + 1 < n and y + 1 < n and grid[x + 1][y] != 1 and grid[x + 1][y + 1] != 1:\n",
    "                        if (x + 1, y, 0) not in tag:\n",
    "                            tag.add((x + 1, y, 0))\n",
    "                            que.append((x + 1, y, 0))\n",
    "                            if x + 1 == n - 1 and y == n - 2:\n",
    "                                return step\n",
    "                        if (x, y, 1) not in tag:\n",
    "                            tag.add((x, y, 1))\n",
    "                            que.append((x, y, 1))\n",
    "                else:\n",
    "                    if x + 2 < n and grid[x + 2][y] != 1:\n",
    "                        if (x + 1, y, 1) not in tag:\n",
    "                            tag.add((x + 1, y, 1))\n",
    "                            que.append((x + 1, y, 1))\n",
    "                    if x + 1 < n and y + 1 < n and grid[x][y + 1] != 1 and grid[x + 1][y + 1] != 1:\n",
    "                        if (x, y + 1, 1) not in tag:\n",
    "                            tag.add((x, y + 1, 1))\n",
    "                            que.append((x, y + 1, 1))\n",
    "                        if (x, y, 0) not in tag:\n",
    "                            tag.add((x, y, 0))\n",
    "                            que.append((x, y, 0))\n",
    "                            if x == n - 1 and y == n - 2:\n",
    "                                return step\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, g: List[List[int]]) -> int:\n",
    "        step, n = 1, len(g)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]  # 初始位置\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):  # 直接把移动后的位置算出来\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)  # 蛇头\n",
    "                    if x2 < n and y2 < n and t not in vis and \\\n",
    "                       g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2:  # 此时蛇头一定在 (n-1,n-1)\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=collections.deque()\n",
    "        q.append((0,1,0,0))\n",
    "        find=set()\n",
    "        while q:\n",
    "            #mark=0 右 mark=1 下\n",
    "            x,y,mark,dist=q.popleft()\n",
    "            if x==m-1 and y==n-1 and mark==0:\n",
    "                return dist\n",
    "            if (x,y,mark) in find:\n",
    "                continue\n",
    "            #print(x,y,mark,dist)\n",
    "            find.add((x,y,mark))\n",
    "            if mark==0 and y+1<n and grid[x][y+1]==0:\n",
    "                q.append((x,y+1,mark,dist+1))\n",
    "            if mark==0 and x+1<m and grid[x+1][y]==0 and grid[x+1][y-1]==0:\n",
    "                q.append((x+1,y,mark,dist+1))\n",
    "            if mark==0 and x+1<m and grid[x+1][y-1]==0 and grid[x+1][y]==0:\n",
    "                #print(\"append\",x+1,y-1,1,dist+1)\n",
    "                q.append((x+1,y-1,1,dist+1))\n",
    "            if mark==1 and y+1<n and grid[x][y+1]==0 and grid[x-1][y+1]==0:\n",
    "                q.append((x,y+1,mark,dist+1))\n",
    "            if mark==1 and x+1<m and grid[x+1][y]==0:\n",
    "                q.append((x+1,y,mark,dist+1))\n",
    "            if mark==1 and y+1<n and grid[x][y+1]==0 and grid[x-1][y+1]==0:\n",
    "                #print(\"append\",x+1,y-1,1,dist+1)\n",
    "                q.append((x-1,y+1,0,dist+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[n-1][n-1] == 1 or grid[n-1][n-2] == 1:\n",
    "            return -1\n",
    "        dist = defaultdict()\n",
    "        dist[(0, 0, 0)] = 0\n",
    "        q = [(0, 0, 0)]\n",
    "        while q:\n",
    "            x, y, state = q.pop(0)\n",
    "            if state == 0:\n",
    "                if y + 2 < n and grid[x][y+2] == 0 and (x, y+1, 0) not in dist:\n",
    "                    dist[(x, y+1, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y+1, 0))\n",
    "                if x + 1 < n and (x+1, y, 0) not in dist and grid[x+1][y] == grid[x+1][y+1] == 0:\n",
    "                    dist[(x+1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x+1, y, 0))\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x+1][y] == grid[x+1][y+1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            else:\n",
    "                if x + 2 < n and (x+1, y, 1) not in dist and grid[x+2][y] == 0:\n",
    "                    dist[(x+1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x+1, y, 1))\n",
    "                if y + 1 < n and (x, y+1, 1) not in dist and grid[x][y+1] == grid[x+1][y+1] == 0:\n",
    "                    dist[(x, y+1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y+1, 1))\n",
    "                if y + 1 < n and x + 1 < n and (x, y, 0) not in dist and grid[x][y+1] == grid[x+1][y+1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "        if (n-1, n-2, 0) in dist:\n",
    "            return dist[(n-1, n-2, 0)]\n",
    "        else:\n",
    "            return -1\n",
    "        \n",
    "        return -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        n, m = len(grid), len(grid[0])\n",
    "        dirs = [\n",
    "            [1, 0, 0],\n",
    "            [0, 1, 0],\n",
    "            [0, 0, 1]\n",
    "        ]\n",
    "        q = [(0, 0, 0)]\n",
    "        vis = {(0, 0, 0)}\n",
    "        \n",
    "        res = 1\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, y, s in tmp:\n",
    "                #蛇尾\n",
    "                for X, Y, S in (x + 1, y, s), (x, y + 1, s), (x, y, s ^ 1):\n",
    "                    head_X = X + S\n",
    "                    head_Y = Y + (1 ^ S)\n",
    "                    if 0 <= X < n and 0 <= Y < m and 0 <= head_X < n and 0 <= head_Y < m:\n",
    "                        if grid[X][Y] == 0 and grid[head_X][head_Y] == 0 and (X, Y, S) not in vis and (s == S or grid[X + 1][Y + 1] == 0):\n",
    "                            if (X, Y) == (n - 1, m - 2):\n",
    "                                return res\n",
    "                            vis.add((X, Y, S))\n",
    "                            q.append((X, Y, S))\n",
    "            res += 1\n",
    "        return -1\n",
    "                            \n",
    "                \n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        # bfs, 网络空间状态搜索\n",
    "        # 怎么表示状态 (x, y, 1) 表示蛇头处于某个位置，然后处于水平还是竖直的状态\n",
    "        n = len(grid)\n",
    "        q = deque([(0, 1, 0)])\n",
    "        step = 0\n",
    "        vis = set([(0, 1, 0)])\n",
    "        def check(x, y):\n",
    "            if 0 <= x < n and 0 <= y < n and grid[x][y] == 0:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        while q:\n",
    "            m = len(q)\n",
    "            for _ in range(m):\n",
    "                x, y, f = q.popleft()\n",
    "                if x == n-1 and y == n-1 and f == 0:\n",
    "                    return step\n",
    "                # 竖直方向\n",
    "                if f == 1:\n",
    "                    dx, dy = x + 1, y\n",
    "                    if check(dx, dy) and (dx, dy, f) not in vis:\n",
    "                        vis.add((dx, dy, f))\n",
    "                        q.append((dx, dy, f))\n",
    "                    dx, dy = x, y + 1\n",
    "                    if check(dx, dy) and check(dx - 1, dy) and (dx, dy, f) not in vis:\n",
    "                        vis.add((dx, dy, f))\n",
    "                        q.append((dx, dy, f))\n",
    "                    dx, dy = x - 1, y + 1\n",
    "                    if check(dx, dy) and check(dx + 1, dy) and (dx, dy, 1 - f) not in vis:\n",
    "                        vis.add((dx, dy, 1 - f))\n",
    "                        q.append((dx, dy, 1 - f))\n",
    "                # 水平方向\n",
    "                else:\n",
    "                    dx, dy = x, y + 1\n",
    "                    if check(dx, dy) and (dx, dy, f) not in vis:\n",
    "                        vis.add((dx, dy, f))\n",
    "                        q.append((dx, dy, f))\n",
    "                    dx, dy = x + 1, y\n",
    "                    if check(dx, dy) and check(dx, dy - 1) and (dx, dy, f) not in vis:\n",
    "                        vis.add((dx, dy, f))\n",
    "                        q.append((dx, dy, f))\n",
    "                    dx, dy = x + 1, y - 1\n",
    "                    if check(dx, dy) and check(dx, dy + 1) and (dx, dy, 1 - f) not in vis:\n",
    "                        vis.add((dx, dy, 1 - f))\n",
    "                        q.append((dx, dy, 1 - f))\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        cur = {(0,1,0)}\n",
    "        hs = {(0,1,0)}\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        cnt = 0\n",
    "        while len(cur) > 0:\n",
    "            \n",
    "            ns = set()\n",
    "            for x,y,d in cur:\n",
    "                if x == m-1 and y == n-1 and d == 0:\n",
    "                    return cnt\n",
    "                if d == 0:\n",
    "                    if x < m - 1 and grid[x+1][y-1] == 0 and grid[x+1][y] == 0:\n",
    "                        ns.add((x+1,y-1,1))\n",
    "                        ns.add((x+1,y,0))\n",
    "                    if y < n - 1 and grid[x][y+1] == 0:\n",
    "                        ns.add((x,y+1,0))\n",
    "                else:\n",
    "                    if y < n - 1 and grid[x-1][y+1] == 0 and grid[x][y+1] == 0:\n",
    "                        ns.add((x-1,y+1,0))\n",
    "                        ns.add((x,y+1,1))\n",
    "                    if x < m-1 and grid[x+1][y] == 0:\n",
    "                        ns.add((x+1,y,1))\n",
    "            ns = ns - hs\n",
    "            hs |= ns\n",
    "            cnt += 1\n",
    "            cur = ns\n",
    "        return -1\n",
    "                \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        step, n = 1, len(grid)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)\n",
    "                    if x2 < n and y2 < n and t not in vis and grid[x][y] == 0 and grid[x2][y2] == 0 and (s == S or grid[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2:\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = deque([(0, 0, 0)])\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        while q:\n",
    "            x, y, status = q.popleft()\n",
    "            if status == 0:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                    dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y + 1, 0))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x + 1, y, 0))\n",
    "                \n",
    "                # 顺时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            else:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y + 1, 1))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                    dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x + 1, y, 1))\n",
    "                \n",
    "                # 逆时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "\n",
    "        return  dist.get((n - 1, n - 2, 0), -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        \n",
    "        start = (0, 0, 'H')\n",
    "        end = (n-1, n-2, 'H')\n",
    "        \n",
    "        visited = set()\n",
    "        visited.add(start)\n",
    "        \n",
    "        queue = deque([(start, 0)])\n",
    "        \n",
    "        while queue:\n",
    "            (r, c, d), steps = queue.popleft()\n",
    "            \n",
    "            if (r, c, d) == end:\n",
    "                return steps\n",
    "            \n",
    "            if d == 'H':\n",
    "                # move right\n",
    "                if c + 2 < n and grid[r][c+2] == 0:\n",
    "                    if (r, c+1, 'H') not in visited:\n",
    "                        visited.add((r, c+1, 'H'))\n",
    "                        queue.append(((r, c+1, 'H'), steps + 1))\n",
    "                # move down\n",
    "                if r + 1 < n and grid[r+1][c] == 0 and grid[r+1][c+1] == 0:\n",
    "                    if (r+1, c, 'H') not in visited:\n",
    "                        visited.add((r+1, c, 'H'))\n",
    "                        queue.append(((r+1, c, 'H'), steps + 1))\n",
    "                    # rotate to vertical\n",
    "                    if (r, c, 'V') not in visited:\n",
    "                        visited.add((r, c, 'V'))\n",
    "                        queue.append(((r, c, 'V'), steps + 1))\n",
    "                        \n",
    "            else:  # d == 'V'\n",
    "                # move down\n",
    "                if r + 2 < n and grid[r+2][c] == 0:\n",
    "                    if (r+1, c, 'V') not in visited:\n",
    "                        visited.add((r+1, c, 'V'))\n",
    "                        queue.append(((r+1, c, 'V'), steps + 1))\n",
    "                # move right\n",
    "                if c + 1 < n and grid[r][c+1] == 0 and grid[r+1][c+1] == 0:\n",
    "                    if (r, c+1, 'V') not in visited:\n",
    "                        visited.add((r, c+1, 'V'))\n",
    "                        queue.append(((r, c+1, 'V'), steps + 1))\n",
    "                    # rotate to horizontal\n",
    "                    if (r, c, 'H') not in visited:\n",
    "                        visited.add((r, c, 'H'))\n",
    "                        queue.append(((r, c, 'H'), steps + 1))\n",
    "                        \n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, g: List[List[int]]) -> int:\n",
    "        step, n = 1, len(g)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]  # 初始位置\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for X, Y, S in tmp:\n",
    "                for t in (X + 1, Y, S), (X, Y + 1, S), (X, Y, S ^ 1):  # 直接把移动后的位置算出来\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)  # 蛇头\n",
    "                    if x2 < n and y2 < n and t not in vis and \\\n",
    "                       g[x][y] == 0 and g[x2][y2] == 0 and (s == S or g[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n - 2:  # 此时蛇头一定在 (n-1,n-1)\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        #BFS记录状态有点技巧\n",
    "        vis={(0,0,0)}\n",
    "        quene=deque()\n",
    "        quene.append((0,0,0))\n",
    "        cnt,n=0,len(grid)\n",
    "        while quene:\n",
    "            m=len(quene)\n",
    "            while m:\n",
    "                cur=quene.popleft()\n",
    "                x,y,s=cur[0],cur[1],cur[2]\n",
    "                if x==n-1 and y==n-2:\n",
    "                    return cnt\n",
    "                dirx=[(x,y+1,s),(x+1,y,s),(x,y,s^1)]\n",
    "                for new_x,new_y,new_s in dirx:\n",
    "                    new_point=(new_x,new_y,new_s)\n",
    "                    if new_s==0 and 0<=new_x<n and 0<=new_y<n-1 and grid[new_x][new_y]==0 and grid[new_x][new_y+1]==0 and (s==new_s or grid[x+1][y+1]==0) and new_point not in vis:\n",
    "                        quene.append((new_x,new_y,new_s))\n",
    "                        vis.add((new_x,new_y,new_s))\n",
    "                    elif new_s==1 and 0<=new_x<n-1 and 0<=new_y<n and grid[new_x][new_y]==0 and grid[new_x+1][new_y]==0 and (s==new_s or grid[x+1][y+1]==0) and new_point not in vis:\n",
    "                     quene.append((new_x,new_y,new_s))\n",
    "                     vis.add((new_x,new_y,new_s))\n",
    "                m-=1\n",
    "            cnt+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        q = deque([(0, 0, 0)])\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                x, y, status = q.popleft()\n",
    "                if status == 0:\n",
    "                    # 向右移动一个单元格\n",
    "                    if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                        dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1\n",
    "                        q.append((x, y + 1, 0))\n",
    "                    \n",
    "                    # 向下移动一个单元格\n",
    "                    if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                        dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                        q.append((x + 1, y, 0))\n",
    "                    \n",
    "                    # 顺时针旋转 90 度\n",
    "                    if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                        dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                        q.append((x, y, 1))\n",
    "                else:\n",
    "                    # 向右移动一个单元格\n",
    "                    if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                        dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                        q.append((x, y + 1, 1))\n",
    "                    \n",
    "                    # 向下移动一个单元格\n",
    "                    if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                        dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                        q.append((x + 1, y, 1))\n",
    "                    \n",
    "                    # 逆时针旋转 90 度\n",
    "                    if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                        dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                        q.append((x, y, 0))\n",
    "\n",
    "        return  dist.get((n - 1, n - 2, 0), -1)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        q = deque([(0,0,0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, status = q.popleft()\n",
    "            if status == 0:\n",
    "                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                    dist[(x, y + 1, 0)]= dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y + 1, 0))\n",
    "                \n",
    "                if x + 1 < n and(x + 1, y, 0) not in dist and grid[x + 1][y] == 0 == grid[x + 1][y + 1]:\n",
    "                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x + 1, y, 0))\n",
    "                \n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            \n",
    "            else:\n",
    "                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y + 1, 1))\n",
    "                \n",
    "                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                    dist[(x + 1,y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x + 1, y, 1))\n",
    "                \n",
    "                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x + 1][y + 1] == grid[x][y + 1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "        return dist.get((n - 1, n - 2, 0), -1)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        #BFS记录状态有点技巧\n",
    "        vis={(0,0,0)}\n",
    "        quene=deque()\n",
    "        quene.append((0,0,0))\n",
    "        cnt,n=0,len(grid)\n",
    "        while quene:\n",
    "            m=len(quene)\n",
    "            while m:\n",
    "                cur=quene.popleft()\n",
    "                x,y,s=cur[0],cur[1],cur[2]\n",
    "                if x==n-1 and y==n-2:\n",
    "                    return cnt\n",
    "                dirx=[(x,y+1,s),(x+1,y,s),(x,y,s^1)]\n",
    "                for new_x,new_y,new_s in dirx:\n",
    "                    new_point=(new_x,new_y,new_s)\n",
    "                    if new_s==0 and 0<=new_x<n and 0<=new_y<n-1 and grid[new_x][new_y]==0 and grid[new_x][new_y+1]==0 and (s==new_s or grid[x+1][y+1]==0) and new_point not in vis:\n",
    "                        quene.append((new_x,new_y,new_s))\n",
    "                        vis.add((new_x,new_y,new_s))\n",
    "                    elif new_s==1 and 0<=new_x<n-1 and 0<=new_y<n and grid[new_x][new_y]==0 and grid[new_x+1][new_y]==0 and (s==new_s or grid[x+1][y+1]==0) and new_point not in vis:\n",
    "                     quene.append((new_x,new_y,new_s))\n",
    "                     vis.add((new_x,new_y,new_s))\n",
    "                m-=1\n",
    "            cnt+=1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS + 位运算优化\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        step, n = 1, len(grid)\n",
    "        vis = {(0, 0, 0)}\n",
    "        q = [(0, 0, 0)]\n",
    "        while q:\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for (X, Y, S) in tmp:\n",
    "                for t in (X, Y + 1, S), (X + 1, Y, S), (X, Y, S ^ 1):\n",
    "                    x, y, s = t\n",
    "                    x2, y2 = x + s, y + (s ^ 1)\n",
    "                    if x2 < n and y2 < n and t not in vis and grid[x][y] == 0 and grid[x2][y2] == 0 and (s == S or grid[x + 1][y + 1] == 0):\n",
    "                        if x == n - 1 and y == n-2:\n",
    "                            return step\n",
    "                        vis.add(t)\n",
    "                        q.append(t)\n",
    "            step += 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        q=collections.deque()\n",
    "        q.append((0,1,0,0))\n",
    "        find=set()\n",
    "        while q:\n",
    "            #mark=0 右 mark=1 下\n",
    "            x,y,mark,dist=q.popleft()\n",
    "            if x==m-1 and y==n-1 and mark==0:\n",
    "                return dist\n",
    "            if (x,y,mark) in find:\n",
    "                continue\n",
    "            print(x,y,mark,dist)\n",
    "            find.add((x,y,mark))\n",
    "            if mark==0 and y+1<n and grid[x][y+1]==0:\n",
    "                q.append((x,y+1,mark,dist+1))\n",
    "            if mark==0 and x+1<m and grid[x+1][y]==0 and grid[x+1][y-1]==0:\n",
    "                q.append((x+1,y,mark,dist+1))\n",
    "            if mark==0 and x+1<m and grid[x+1][y-1]==0 and grid[x+1][y]==0:\n",
    "                #print(\"append\",x+1,y-1,1,dist+1)\n",
    "                q.append((x+1,y-1,1,dist+1))\n",
    "            if mark==1 and y+1<n and grid[x][y+1]==0 and grid[x-1][y+1]==0:\n",
    "                q.append((x,y+1,mark,dist+1))\n",
    "            if mark==1 and x+1<m and grid[x+1][y]==0:\n",
    "                q.append((x+1,y,mark,dist+1))\n",
    "            if mark==1 and y+1<n and grid[x][y+1]==0 and grid[x-1][y+1]==0:\n",
    "                #print(\"append\",x+1,y-1,1,dist+1)\n",
    "                q.append((x-1,y+1,0,dist+1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        q = deque([(0, 0, 0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, status = q.popleft()\n",
    "            if status == 0:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                    dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y + 1, 0))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x + 1, y, 0))\n",
    "                \n",
    "                # 顺时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            else:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y + 1, 1))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                    dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x + 1, y, 1))\n",
    "                \n",
    "                # 逆时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "\n",
    "        return dist.get((n - 1, n - 2, 0), -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        q = deque([(0, 0, 0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, status = q.popleft()\n",
    "            if status == 0:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                    dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y + 1, 0))\n",
    "\n",
    "                # 向下移动一个单元格\n",
    "                if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x + 1, y, 0))\n",
    "\n",
    "                # 顺时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            else:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y + 1, 1))\n",
    "\n",
    "                # 向下移动一个单元格\n",
    "                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                    dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x + 1, y, 1))\n",
    "\n",
    "                # 逆时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "\n",
    "        return dist.get((n - 1, n - 2, 0), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid) \n",
    "        Q = deque([(0, 0,0,0,1)])\n",
    "        vis = set() \n",
    "        vis.add((0,0,0,1))\n",
    "        def check(x1,y1,x2,y2):\n",
    "            return 0<=x1<n and 0<=y1<n and 0<=x2<n and 0<=y2<n\n",
    "\n",
    "        while Q:\n",
    "            d, x1, y1, x2, y2 = Q.popleft() \n",
    "            if (x1,y1) == (n-1,n-2) and (x2,y2) == (n-1,n-1):\n",
    "                return d \n",
    "            for nx1,ny1,nx2,ny2 in [[x1,y1+1,x2,y2+1], [x1+1,y1,x2+1,y2]]:\n",
    "                if check(nx1,ny1,nx2,ny2) and grid[nx1][ny1] == grid[nx2][ny2] == 0 and (nx1,ny1,nx2,ny2) not in vis:\n",
    "                    vis.add((nx1,ny1,nx2,ny2))\n",
    "                    Q.append((d+1, nx1,ny1,nx2,ny2))\n",
    "            if x1 == x2 and y2 == y1 + 1 and x1 < n-1 and grid[x1+1][y1] == grid[x2+1][y2] == 0:\n",
    "                nx1,ny1,nx2,ny2 = x1,y1,x2+1,y2-1\n",
    "                if check(nx1,ny1,nx2,ny2) and (nx1,ny1,nx2,ny2) not in vis:\n",
    "                    vis.add((nx1,ny1,nx2,ny2))\n",
    "                    Q.append((d+1, nx1,ny1,nx2,ny2))\n",
    "            if y1 == y2 and x2 == x1 + 1 and y1 < n-1 and grid[x1][y1+1] == grid[x2][y2+1] == 0:\n",
    "                nx1,ny1,nx2,ny2 = x1,y1,x2-1,y2+1\n",
    "                if check(nx1,ny1,nx2,ny2) and (nx1,ny1,nx2,ny2) not in vis:\n",
    "                    vis.add((nx1,ny1,nx2,ny2))\n",
    "                    Q.append((d+1, nx1,ny1,nx2,ny2))\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        vis=set()\n",
    "        n=len(grid)\n",
    "        stack=collections.deque()\n",
    "        stack.append([0,0,0,0,1])\n",
    "        while stack:\n",
    "            d,x1,y1,x2,y2=stack.popleft()\n",
    "            if (x1,y1,x2,y2) in vis:\n",
    "                continue\n",
    "            vis.add((x1,y1,x2,y2))\n",
    "            if x1==n-1 and y1==n-2 and x2==n-1 and y2==n-1:\n",
    "                return d \n",
    "            if y2+1<n and grid[x2][y2+1]!=1 and y1+1<n and grid[x1][y1+1]!=1:\n",
    "                if (x1,y1+1,x2,y2+1) not in vis:\n",
    "                    stack.append([d+1,x1,y1+1,x2,y2+1])\n",
    "            if x2+1<n and grid[x2+1][y2]!=1 and x1+1<n and grid[x1+1][y1]!=1:\n",
    "                if (x1+1,y1,x2+1,y2) not in vis:\n",
    "                    stack.append([d+1,x1+1,y1,x2+1,y2] )\n",
    "\n",
    "            if x1==x2 and y1+1==y2:\n",
    "                if x1+1<n and grid[x1+1][y1]!=1 and grid[x2+1][y2]!=1:\n",
    "                    if (x1,y1,x1+1,y1) not in vis:\n",
    "                        stack.append([d+1,x1,y1,x1+1,y1])\n",
    "            if y1==y2 and x1+1==x2:\n",
    "                if y1+1<n and grid[x1][y1+1]!=1 and grid[x2][y2+1]!=1:\n",
    "                    if (x1,y1,x1,y1+1) not in vis:\n",
    "                        stack.append([d+1,x1,y1,x1,y1+1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: list[list[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        dist = {(0, 0, 0): 0}\n",
    "        q = deque([(0, 0, 0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, status = q.popleft()\n",
    "            if status == 0:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 2 < n and (x, y + 1, 0) not in dist and grid[x][y + 2] == 0:\n",
    "                    dist[(x, y + 1, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y + 1, 0))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 1 < n and (x + 1, y, 0) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x + 1, y, 0)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x + 1, y, 0))\n",
    "                \n",
    "                # 顺时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 1) not in dist and grid[x + 1][y] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 1)] = dist[(x, y, 0)] + 1\n",
    "                    q.append((x, y, 1))\n",
    "            else:\n",
    "                # 向右移动一个单元格\n",
    "                if y + 1 < n and (x, y + 1, 1) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y + 1, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y + 1, 1))\n",
    "                \n",
    "                # 向下移动一个单元格\n",
    "                if x + 2 < n and (x + 1, y, 1) not in dist and grid[x + 2][y] == 0:\n",
    "                    dist[(x + 1, y, 1)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x + 1, y, 1))\n",
    "                \n",
    "                # 逆时针旋转 90 度\n",
    "                if x + 1 < n and y + 1 < n and (x, y, 0) not in dist and grid[x][y + 1] == grid[x + 1][y + 1] == 0:\n",
    "                    dist[(x, y, 0)] = dist[(x, y, 1)] + 1\n",
    "                    q.append((x, y, 0))\n",
    "\n",
    "        return dist.get((n - 1, n - 2, 0), -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = {(0, 0, 0, 1)}\n",
    "        stack = deque([[0, 0, 0, 0, 1]])\n",
    "        while stack:\n",
    "            d, r1, c1, r2, c2 = stack.popleft()\n",
    "            if (r1, c1, r2, c2) == (n-1, n-2, n-1, n-1):\n",
    "                return d\n",
    "            if r1 == r2:\n",
    "                if c2+1<n and grid[r1][c2+1] == 0 and (r1, c2, r1, c2+1) not in visit:\n",
    "                    visit.add((r1, c2, r1, c2+1))\n",
    "                    stack.append([d+1, r1, c2, r1, c2+1])\n",
    "                if r1+1<m and grid[r1+1][c1] == grid[r1+1][c2] == 0 and (r1+1, c1, r1+1, c2) not in visit:\n",
    "                    visit.add((r1+1, c1, r1+1, c2))\n",
    "                    stack.append([d+1, r1+1, c1, r1+1, c2])\n",
    "                if r1+1<m and grid[r1+1][c1] == grid[r1+1][c2] == 0 and (r1, c1, r1+1, c1) not in visit:\n",
    "                    visit.add((r1, c1, r1+1, c1))\n",
    "                    stack.append([d+1, r1, c1, r1+1, c1])\n",
    "            if c1 == c2:\n",
    "                if r2+1<n and grid[r2+1][c1] == 0 and (r1+1, c1, r2+1, c2) not in visit:\n",
    "                    visit.add((r1+1, c1, r2+1, c2))\n",
    "                    stack.append([d+1, r1+1, c1, r2+1, c2])\n",
    "                if c1+1<n and grid[r1][c1+1] == grid[r2][c2+1] == 0 and (r1, c1+1, r2, c2+1) not in visit:\n",
    "                    visit.add((r1, c1+1, r2, c2+1))\n",
    "                    stack.append([d+1, r1, c1+1, r2, c2+1])\n",
    "                if c1+1<n and grid[r1][c1+1] == grid[r2][c2+1] == 0 and (r1, c1, r1, c1+1) not in visit:\n",
    "                    visit.add((r1, c1, r1, c1+1))\n",
    "                    stack.append([d+1, r1, c1, r1, c1+1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        if grid[n - 1][n - 1] == 1 or grid[n - 1][n - 2] == 1:\n",
    "            return -1\n",
    "\n",
    "\n",
    "        queue = collections.deque([(0,0,0,1,0)]) # taili, tailj, headi, headj, dir\n",
    "        seen = set()\n",
    "        seen.add((0,0,0,1,0))\n",
    "        step = 0\n",
    "        while queue:\n",
    "            size = len(queue)\n",
    "            for _ in range(size):\n",
    "                ti, tj, hi, hj, dirs = queue.popleft()\n",
    "                if ti == n - 1 and tj == n - 2 and hi == n - 1 and hj == n - 1 and dirs == 0:\n",
    "                    return step\n",
    "\n",
    "                if dirs == 0:\n",
    "                    if hj + 1 < n and grid[hi][hj + 1] == 0 and (hi, hj, hi, hj + 1, dirs) not in seen:\n",
    "                        queue.append((hi, hj, hi, hj + 1, dirs))\n",
    "                        seen.add((hi, hj, hi, hj + 1, dirs))\n",
    "                    \n",
    "                    if ti + 1 < n and hi + 1 < n and grid[ti + 1][tj] == 0 and grid[hi + 1][hj] == 0 and (ti + 1, tj, hi + 1, hj, dirs) not in seen:\n",
    "                        queue.append((ti + 1, tj, hi + 1, hj, dirs))\n",
    "                        seen.add((ti + 1, tj, hi + 1, hj, dirs))\n",
    "\n",
    "                    if ti + 1 < n and grid[ti + 1][tj] == 0 and grid[ti + 1][tj + 1] == 0 and (ti, tj, ti + 1, tj, 1) not in seen:\n",
    "                        queue.append((ti, tj, ti + 1, tj, 1))\n",
    "                        seen.add((ti, tj, ti + 1, tj, 1))\n",
    "                else: # dirs == 1\n",
    "                    if tj +1 < n and hj + 1 < n and grid[ti][tj + 1] == 0 and grid[hi][hj + 1] == 0 and (ti, tj + 1, hi, hj + 1, 1) not in seen:\n",
    "                        queue.append((ti, tj + 1, hi, hj + 1, 1))\n",
    "                        seen.add((ti, tj + 1, hi, hj + 1, 1))\n",
    "                    \n",
    "                    if hi + 1 < n and grid[hi + 1][hj] == 0 and (hi, hj, hi + 1, hj, 1) not in seen:\n",
    "                        queue.append((hi, hj, hi + 1, hj, 1))\n",
    "                        seen.add((hi, hj, hi + 1, hj, 1))\n",
    "\n",
    "                    if tj + 1 < n and grid[ti][tj + 1] == 0 and grid[ti + 1][tj + 1] == 0 and (ti, tj, ti, tj + 1, 0) not in seen:\n",
    "                        queue.append((ti, tj, ti, tj + 1, 0))\n",
    "                        seen.add((ti, tj, ti, tj + 1, 0))\n",
    "\n",
    "            step += 1\n",
    "\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        cands = [(i, j) for i, j in product(range(3), range(3)) if not grid[i][j]]\n",
    "        available = [(i, j) for i, j in product(range(3), range(3)) if grid[i][j] > 1]\n",
    "        \n",
    "        \n",
    "        def backtrack(i):\n",
    "            if i == len(cands):\n",
    "                return 0\n",
    "            \n",
    "            ans = float('inf')\n",
    "            x, y = cands[i]\n",
    "            for j in range(len(available)):\n",
    "                a, b = available[j]\n",
    "                if grid[a][b] > 1:\n",
    "                    grid[a][b] -= 1\n",
    "                    ans = min(ans, abs(x - a) + abs(y - b) + backtrack(i+1))\n",
    "                    grid[a][b] += 1\n",
    "            return ans\n",
    "        \n",
    "        return backtrack(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        from_ = []\n",
    "        to = []\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, cnt in enumerate(row):\n",
    "                if cnt > 1:\n",
    "                    from_.extend([(i, j)] * (cnt - 1))\n",
    "                elif cnt == 0:\n",
    "                    to.append((i, j))\n",
    "\n",
    "        ans = inf\n",
    "        for from2 in permutations(from_):\n",
    "            total = 0\n",
    "            for (x1, y1), (x2, y2) in zip(from2, to):\n",
    "                total += abs(x1 - x2) + abs(y1 - y2)\n",
    "            ans = min(ans, total)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        st = []\n",
    "        to = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if grid[i][j] > 1:\n",
    "                    for _ in range(grid[i][j]-1):\n",
    "                        st.append((i, j))\n",
    "                elif grid[i][j] == 0:\n",
    "                    # print(i, j)\n",
    "                    to.append((i, j))\n",
    "        # print(to)\n",
    "        # print(st) \n",
    "        def helper(idices):\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(len(idices)):\n",
    "                j = idices[i]\n",
    "                ans += abs(st[i][0] - to[j][0]) + abs(st[i][1] - to[j][1])\n",
    "            return ans\n",
    "            \n",
    "        ans = inf\n",
    "        for idices in permutations(range(len(to)), len(to)):\n",
    "            ans = min(ans, helper(idices))\n",
    "        return ans\n",
    "                    \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = 3\n",
    "        s = []\n",
    "        e = []\n",
    "        mp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]>1:\n",
    "                    s.append((i,j))\n",
    "                    mp[i][j] = grid[i][j]-1\n",
    "                elif grid[i][j]<1:\n",
    "                    e.append((i,j))\n",
    "        ans = inf\n",
    "        def dfs(i,cnt):\n",
    "            if i==len(e):\n",
    "                nonlocal ans\n",
    "                ans = min(ans,cnt)\n",
    "                return\n",
    "            for x,y in s:\n",
    "                if mp[x][y]>0:\n",
    "                    mp[x][y]-=1\n",
    "                    le = abs(x-e[i][0])+abs(y-e[i][1])\n",
    "                    dfs(i+1,cnt+le)\n",
    "                    mp[x][y]+=1\n",
    "        dfs(0,0)        \n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        @cache\n",
    "        def f(m):\n",
    "            if m == (1,1,1,1,1,1,1,1,1): return 0\n",
    "            res = []\n",
    "            for i in range(9):\n",
    "                if m[i] == 0:\n",
    "                    for j in range(9):\n",
    "                        if m[j] > 1: \n",
    "                            l = list(m)\n",
    "                            l[i] = 1\n",
    "                            l[j] -= 1\n",
    "                            p = abs(i//3-j//3) + abs(i%3-j%3)\n",
    "                            res.append(p+f(tuple(l)))\n",
    "            return min(res)\n",
    "        return f(tuple(sum(grid, [])))\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "class Solution:\r\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\r\n",
    "        ans = 0\r\n",
    "        val = 0\r\n",
    "        for i in range(3):\r\n",
    "            for j in range(3):\r\n",
    "                val = val*10 + grid[i][j]\r\n",
    "        queue = deque([val])\r\n",
    "        visited = set([val])\r\n",
    "        while queue:\r\n",
    "            l = len(queue)\r\n",
    "            for _ in range(l):\r\n",
    "                cur = queue.popleft()\r\n",
    "                if cur == 111111111:\r\n",
    "                    return ans\r\n",
    "                val = cur\r\n",
    "                for i in range(8, -1, -1):\r\n",
    "                    x, y = i//3, i%3\r\n",
    "                    temp = val%10\r\n",
    "                    val //= 10\r\n",
    "                    if temp > 1:\r\n",
    "                        for dx, dy in [[1,0],[-1,0],[0,1],[0,-1]]:\r\n",
    "                            nx, ny = x+dx, y+dy\r\n",
    "                            if 0<=nx<3 and 0<=ny<3:\r\n",
    "                                nex = cur + 10**(8-(3*nx+ny)) - 10**(8-(3*x+y))\r\n",
    "                                if nex not in visited:\r\n",
    "                                    visited.add(nex)\r\n",
    "                                    queue.append(nex)\r\n",
    "            ans += 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        s1, s2 = '', ''\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if grid[i][j] == 0:\n",
    "                    s1 += str(3 * i + j)\n",
    "                elif grid[i][j] > 1:\n",
    "                    s2 += str(3 * i + j) + str(grid[i][j])\n",
    "        k = len(s1)\n",
    "        res = ''\n",
    "        for _ in range(k):\n",
    "            res += '-'\n",
    "\n",
    "        def get(c: int, c1: int) -> int:\n",
    "            x1, y1 = c // 3, c % 3\n",
    "            x2, y2 = c1 // 3, c1 % 3\n",
    "            return abs(x1 - x2) + abs(y1 - y2)\n",
    "\n",
    "        def do(s: str, idx: int) -> str:\n",
    "            lis = list(s)\n",
    "            lis[idx] = '-'\n",
    "            return ''.join(c for c in lis)\n",
    "\n",
    "        def do1(ss: str, idx: int) -> str:\n",
    "            lis = list(ss)\n",
    "            lis[idx] = str(int(lis[idx]) - 1)\n",
    "            return ''.join(c for c in lis)\n",
    "\n",
    "        @cache\n",
    "        def dfs(s: str, ss: str) -> int:\n",
    "            if s == res:\n",
    "                return 0\n",
    "            ans = 10 ** 9\n",
    "            for idx, c in enumerate(s):\n",
    "                if c == '-':\n",
    "                    continue\n",
    "                l = len(ss)\n",
    "                for t in range(0, l, 2):\n",
    "                    c1, v = int(ss[t]), int(ss[t + 1])\n",
    "                    if v == 1:\n",
    "                        continue\n",
    "                    ans = min(ans, dfs(do(s, idx), do1(ss, t + 1)) + get(int(c), c1))\n",
    "            return ans\n",
    "\n",
    "        return dfs(s1, s2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        target = [1] * 9\n",
    "\n",
    "        st = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                st.append(grid[i][j]) \n",
    "        vis = set()\n",
    "        vis.add(tuple(st))\n",
    "        q = deque([st])\n",
    "\n",
    "        step = 0\n",
    "        while q:\n",
    "            for _ in range(len(q)):\n",
    "                cur = list(q.popleft())\n",
    "                if cur == target:\n",
    "                    return step\n",
    "                for i in range(9):\n",
    "                    if cur[i] > 1:\n",
    "                        t = cur[:]\n",
    "                        x, y = i // 3, i % 3\n",
    "                        for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                            if 0 <= nx < 3 and 0 <= ny < 3:\n",
    "                                t[nx * 3 + ny] += 1\n",
    "                                t[x * 3 + y] -= 1\n",
    "                                if tuple(t) not in vis:\n",
    "                                    vis.add(tuple(t))\n",
    "                                    q.append(t[:])\n",
    "                                t[nx * 3 + ny] -= 1 \n",
    "                                t[x * 3 + y] += 1\n",
    "            step += 1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        que = deque()\n",
    "        status = tuple(grid[i //3][i%3] for i in range(9))\n",
    "        seen = set()\n",
    "        seen.add(status)\n",
    "        que.append([0, status])\n",
    "        while que:\n",
    "            step, status = que.popleft()\n",
    "            if max(status) == 1:\n",
    "                return step\n",
    "            for i in range(9):\n",
    "                if status[i] <= 1:\n",
    "                    continue\n",
    "                if status[i] > 1:\n",
    "                    if i + 3 < 9:\n",
    "                        buf = list(status)\n",
    "                        buf[i] -= 1\n",
    "                        buf[i + 3] += 1\n",
    "                        t = tuple(buf)\n",
    "                        if t not in seen:\n",
    "                            seen.add(t)\n",
    "                            que.append([step + 1, t])\n",
    "                    if i - 3 >= 0:\n",
    "                        buf = list(status)\n",
    "                        buf[i] -= 1\n",
    "                        buf[i -3] += 1\n",
    "                        t = tuple(buf)\n",
    "                        if t not in seen:\n",
    "                            seen.add(t)\n",
    "                            que.append([step + 1, t])\n",
    "                    if i % 3 != 0 and i - 1 >= 0:\n",
    "                        buf = list(status)\n",
    "                        buf[i] -= 1\n",
    "                        buf[i -1] += 1\n",
    "                        t = tuple(buf)\n",
    "                        if t not in seen:\n",
    "                            seen.add(t)\n",
    "                            que.append([step + 1, t])\n",
    "                    if i % 3 != 2 and i + 1 < 9:\n",
    "                        buf = list(status)\n",
    "                        buf[i] -= 1\n",
    "                        buf[i +1] += 1\n",
    "                        t = tuple(buf)\n",
    "                        if t not in seen:\n",
    "                            seen.add(t)\n",
    "                            que.append([step + 1, t])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:        \n",
    " \n",
    "        res = []\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "\n",
    "                res.append(grid[i][j])\n",
    "\n",
    "        directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]\n",
    "        \n",
    "        vis = set()\n",
    "        vis.add(tuple(res))\n",
    "    \n",
    "        queue = deque([(res, 0)])\n",
    "        while queue:\n",
    "            arr, step = queue.popleft()\n",
    "            if arr == [1,1,1,1,1,1,1,1,1]:\n",
    "                return step\n",
    "            for i in range(9):\n",
    "                if arr[i] >= 2:\n",
    "                    for choice in directions:\n",
    "                        nx = i // 3 + choice[0]\n",
    "                        ny = i % 3 + choice[1]\n",
    "                        if 0 <= nx < 3 and 0 <= ny < 3:\n",
    "                            arr[nx * 3 + ny] += 1\n",
    "                            arr[i] -= 1\n",
    "                            if tuple(arr) not in vis:\n",
    "                                queue.append((arr.copy(), step + 1))\n",
    "                                vis.add(tuple(arr))\n",
    "                            arr[i] += 1\n",
    "                            arr[nx * 3 + ny] -= 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        d={\n",
    "            0:[1,3],\n",
    "            1:[0,2,4],\n",
    "            2:[1,5],\n",
    "            3:[0,4,6],\n",
    "            4:[1,3,5,7],\n",
    "            5:[2,4,8],\n",
    "            6:[3,7],\n",
    "            7:[4,6,8],\n",
    "            8:[5,7],\n",
    "        }\n",
    "        rem=set()\n",
    "        find=False\n",
    "        ans=-1\n",
    "        q=collections.deque()\n",
    "        st=\"\"\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                st+=str(grid[i][j])\n",
    "        q.append((0,st))\n",
    "        while q:\n",
    "            now,s=q.popleft()\n",
    "            if find :\n",
    "                break \n",
    "            if s==\"111111111\":\n",
    "                find=True\n",
    "                return now\n",
    "            if s in rem:\n",
    "                continue \n",
    "            rem.add(s)\n",
    "            ls=list(s)\n",
    "            #print(s)\n",
    "            for i in range(9):\n",
    "                if ls[i]==\"0\" or ls[i]==\"1\":\n",
    "                    continue\n",
    "                #print(s,i,ls[i])\n",
    "                ls[i]=chr(ord(ls[i])-1)\n",
    "                for j in d[i]:\n",
    "                    ls[j]=chr(ord(ls[j])+1)\n",
    "                    if int(ls[j])<6:\n",
    "                        q.append((now+1,\"\".join(ls)))\n",
    "                    ls[j]=chr(ord(ls[j])-1)\n",
    "                ls[i]=chr(ord(ls[i])+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "'''\n",
    "最小费用最大流，洛谷 P3381\n",
    "'''\n",
    "from collections import *\n",
    "from math import *\n",
    "\n",
    "class Node:\n",
    "    def __init__(self):\n",
    "        self.val, self.v, self.next, self.w = 0, 0, 0, 0\n",
    "    def __str__(self):\n",
    "        return \"{}, {}, {}, {}\".format(self.val, self.v, self.next, self.w)\n",
    "\n",
    "class Dinic:\n",
    "    def __init__(self, s, t):\n",
    "        self.nodes = [Node() for _ in range(10110)]\n",
    "        self.top = 1\n",
    "        self.s, self.t = s, t\n",
    "        self.N = 5010\n",
    "        self.head, self.vis, self.dist = [0] * self.N, [0] * self.N, [inf] * self.N\n",
    "        self.cost, self.maxflow = 0, 0\n",
    "    \n",
    "    def _add_edge(self, u, v, val, w):\n",
    "        self.top += 1\n",
    "        self.nodes[self.top].v = v\n",
    "        self.nodes[self.top].w = w\n",
    "        self.nodes[self.top].val = val\n",
    "        self.nodes[self.top].next = self.head[u]\n",
    "        self.head[u] = self.top\n",
    "    \n",
    "    def add_edge(self, u, v, val, w):\n",
    "        self._add_edge(u , v, val, w)\n",
    "        self._add_edge(v, u, 0, -w)\n",
    "    \n",
    "    def spfa(self)->bool:\n",
    "        self.vis, self.dist = [0] * self.N, [inf] * self.N\n",
    "        self.dist[self.s], self.vis[self.s] = 0, 1\n",
    "        dq = deque([self.s])\n",
    "        \n",
    "        while dq:\n",
    "            u = dq.popleft()\n",
    "            self.vis[u] = 0\n",
    "            i = self.head[u]\n",
    "            while i:\n",
    "                d = self.nodes[i].v\n",
    "                if self.dist[u] + self.nodes[i].w < self.dist[d] and self.nodes[i].val:\n",
    "                    self.dist[d] = self.dist[u] + self.nodes[i].w\n",
    "                    if self.vis[d] == 0: \n",
    "                        dq.append(d)\n",
    "                        self.vis[d] = 1\n",
    "                i = self.nodes[i].next\n",
    "        return self.dist[self.t] != inf\n",
    "    \n",
    "    def dfs(self, u, flow)->int:\n",
    "        if u == self.t:\n",
    "            self.vis[self.t] = 1\n",
    "            self.maxflow += flow\n",
    "            return flow\n",
    "        used = 0\n",
    "        self.vis[u] = 1\n",
    "        i = self.head[u]\n",
    "        while i:\n",
    "            d = self.nodes[i].v\n",
    "            if (self.vis[d] == 0 or d == self.t) and self.nodes[i].val != 0 and self.dist[d] == self.dist[u] + self.nodes[i].w:\n",
    "                minflow = self.dfs(d, min(flow-used, self.nodes[i].val))\n",
    "                if minflow != 0:\n",
    "                    self.cost += self.nodes[i].w * minflow\n",
    "                    self.nodes[i].val -= minflow\n",
    "                    self.nodes[i^1].val += minflow\n",
    "                    used += minflow\n",
    "                if used == flow: break\n",
    "            i = self.nodes[i].next\n",
    "        return used\n",
    "\n",
    "    def get_min_cost_max_flow(self):\n",
    "        while self.spfa():\n",
    "            self.vis[self.t] = 1\n",
    "            while self.vis[self.t]:\n",
    "                self.vis = [0] * self.N\n",
    "                self.dfs(self.s, inf)\n",
    "        return self.maxflow, self.cost\n",
    "\n",
    "# if __name__ == '__main__':\n",
    "#     n, m, s, t = map(int, input().split())\n",
    "#     dinic = Dinic(s, t)\n",
    "#     for i in range(m):\n",
    "#         u, v, val, w = map(int, input().split())\n",
    "#         dinic.add_edge(u , v, val, w)\n",
    "#         dinic.add_edge(v, u, 0, -w)\n",
    "#     ans, cost = dinic.get_min_cost_max_flow()\n",
    "#     print(ans, cost)\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        src = 9\n",
    "        dst = 10\n",
    "        dinic = Dinic(src, dst)\n",
    "        _from, _to = [], []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] > 1:\n",
    "                    _from.append((i, j, grid[i][j] - 1))\n",
    "                elif grid[i][j] == 0:\n",
    "                    _to.append((i, j))\n",
    "\n",
    "        for x1, y1, w in _from:\n",
    "            u = x1 * m + y1\n",
    "            dinic.add_edge(src, u, w, 0)\n",
    "            for x2, y2 in _to:\n",
    "                v = x2 * m + y2\n",
    "                dinic.add_edge(u, v, 1, abs(x1-x2)+abs(y1-y2))\n",
    "        for x2, y2 in _to:\n",
    "            v = x2 * m + y2\n",
    "            dinic.add_edge(v, dst, 1, 0)\n",
    "        flow, cost = dinic.get_min_cost_max_flow()\n",
    "\n",
    "        return cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        d=[]\n",
    "        e=[]\n",
    "        for i in range(3):\n",
    "            for j in range(3):\n",
    "                if grid[i][j]>1:\n",
    "                    d.append([i,j,grid[i][j]-1])\n",
    "                elif grid[i][j]==0:\n",
    "                    e.append([i,j])\n",
    "        c=[[] for i in range(len(d))]\n",
    "        k=0\n",
    "        for i in d:\n",
    "            for j in e:\n",
    "                c[k].append(abs(i[0]-j[0])+abs(i[1]-j[1]))\n",
    "            k+=1\n",
    "        e=[]\n",
    "        k=0\n",
    "        for i in d:\n",
    "            e.append(i[2]+k)\n",
    "            k+=i[2]\n",
    "        d=[]\n",
    "        def get(l,n,ans,t):\n",
    "            if len(l)==len(c[0]):\n",
    "                d.append(ans)\n",
    "                return\n",
    "            for i in range(len(c[n])):\n",
    "                if i not in l:\n",
    "                    if len(l)+1<e[t]:\n",
    "                        get(l+[i],n,ans+c[n][i],t)\n",
    "                    else :\n",
    "                        get(l+[i],n+1,ans+c[n][i],t+1)\n",
    "        get([],0,0,0)\n",
    "        return min(d)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        target = n * n\n",
    "        visited = set()\n",
    "\n",
    "        def check_state(state):\n",
    "            return tuple(map(tuple, state)) not in visited\n",
    "\n",
    "        def move_count(state):\n",
    "            return sum(row.count(1) for row in state)\n",
    "\n",
    "        def find_neighbors(state):\n",
    "            neighbors = []\n",
    "            for r in range(n):\n",
    "                for c in range(n):\n",
    "                    if state[r][c] > 1:\n",
    "                        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:\n",
    "                            nr, nc = r + dr, c + dc\n",
    "                            if 0 <= nr < n and 0 <= nc < n:\n",
    "                                new_state = [row[:] for row in state]\n",
    "                                new_state[r][c] -= 1\n",
    "                                new_state[nr][nc] += 1\n",
    "                                neighbors.append(new_state)\n",
    "            return neighbors\n",
    "\n",
    "        start_state = [list(row) for row in grid]\n",
    "        queue = deque([(start_state, 0)])\n",
    "        visited.add(tuple(map(tuple, start_state)))\n",
    "\n",
    "        while queue:\n",
    "            state, moves = queue.popleft()\n",
    "            if move_count(state) == target:\n",
    "                return moves\n",
    "            for neighbor in find_neighbors(state):\n",
    "                if check_state(neighbor):\n",
    "                    queue.append((neighbor, moves + 1))\n",
    "                    visited.add(tuple(map(tuple, neighbor)))\n",
    "\n",
    "        return -1  # 如果无法达到目标状态"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "e = [(i, i + 1) for i in range(9) if (i + 1) % 3] + [(i, i + 3) for i in range(6)]\n",
    "res = {}\n",
    "q = [(1,) * 9]\n",
    "res[q[0]] = step = 0\n",
    "while q:\n",
    "    step += 1\n",
    "    nq = []\n",
    "    for t in q:\n",
    "        for i, j in e:\n",
    "            if t[i] and (nt := t[:i] + (t[i] - 1,) + t[i + 1 : j] + (t[j] + 1,) + t[j + 1 :]) not in res:\n",
    "                res[nt] = step\n",
    "                nq.append(nt)\n",
    "            if t[j] and (nt := t[:i] + (t[i] + 1,) + t[i + 1 : j] + (t[j] - 1,) + t[j + 1 :]) not in res:\n",
    "                res[nt] = step\n",
    "                nq.append(nt)\n",
    "    q = nq\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        return res[tuple(chain(*grid))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "init = (1,) * 9\n",
    "q = [init]\n",
    "vis = {init: 0}\n",
    "while q:\n",
    "    new = []\n",
    "    for pre in q:\n",
    "        state = list(pre)\n",
    "        for i in range(9):\n",
    "            if state[i] > 0:\n",
    "                x, y = divmod(i, 3)\n",
    "                for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                    if 0 <= nx < 3 and 0 <= ny < 3:\n",
    "                        ni = nx * 3 + ny\n",
    "                        state[i] -= 1\n",
    "                        state[ni] += 1\n",
    "                        t = tuple(state)\n",
    "                        if t not in vis:\n",
    "                            vis[t] = vis[pre] + 1\n",
    "                            new.append(t)\n",
    "                        state[i] += 1\n",
    "                        state[ni] -= 1\n",
    "    q = new\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        return vis[tuple(v for row in grid for v in row)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        emp = []\n",
    "        more = []\n",
    "        for i,g in enumerate(grid):\n",
    "            for j,x in enumerate(g):\n",
    "                if x == 0:\n",
    "                    emp += [i,j],\n",
    "                while x > 1:\n",
    "                    more += [i,j],\n",
    "                    x -= 1\n",
    "        # print(more, emp)\n",
    "        ways = list(permutations(more, len(more)))\n",
    "        # print(ways)\n",
    "        ans = inf\n",
    "        for way in ways:\n",
    "            tem = sum(abs(x1-x2)+abs(y1-y2) for (x1,y1),(x2,y2) in zip(emp, way) )\n",
    "            if tem < ans:\n",
    "                ans = tem\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid: List[List[int]]) -> int:\n",
    "        res = []\n",
    "        num = []\n",
    "        ans = 10000000\n",
    "        for i in range(0,3):\n",
    "            for j in range(0,3):\n",
    "                if grid[i][j] >1:\n",
    "                    for cnt in range(grid[i][j]-1):\n",
    "                        res.append([i,j])\n",
    "                if grid[i][j] ==0:\n",
    "                    num.append([i,j])\n",
    "        all = list(itertools.permutations(res))\n",
    "        for t in all:\n",
    "            tp=0\n",
    "            for i in range(len(num)):\n",
    "                tp+=abs(t[i][0]-num[i][0])+abs(t[i][1]-num[i][1])\n",
    "            ans=min(ans,tp)\n",
    "        return ans\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumMoves(self, grid):\n",
    "        remove = []\n",
    "        to = []\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, cnt in enumerate(row):\n",
    "                if cnt > 1:\n",
    "                    remove.extend([(i, j)] * (cnt - 1))\n",
    "                elif cnt == 0:\n",
    "                    to.append((i, j))\n",
    "        res = []\n",
    "        n = len(remove)\n",
    "        self.dfs(remove, n, [], [False for i in range(n)], res)\n",
    "        minR = float(\"inf\")\n",
    "        for i in res:\n",
    "            total = 0\n",
    "            for j, e in enumerate(i):\n",
    "                total += abs(e[0] - to[j][0]) + abs(e[1] - to[j][1])\n",
    "            minR = min(minR, total)\n",
    "        return minR\n",
    "\n",
    "        # 全排列\n",
    "    def dfs(self, remove, n, r,  visited, res):\n",
    "        if len(r) == n:\n",
    "            res.append(r[:])\n",
    "            return\n",
    "        for i in range(n):\n",
    "            if not visited[i]:\n",
    "                visited[i] = True\n",
    "                r.append(remove[i])\n",
    "                self.dfs(remove, n, r, visited, res)\n",
    "                r.pop()\n",
    "                visited[i] = False"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
